Herzlich willkommen! Wir befassen uns heute mit einem algorithmischen Thema, dass wir also nicht

nur deswegen analysieren, weil wir mal was analysieren wollen, so wie bisher, sondern

dass uns eben als algorithmisches Thema an sich interessiert, neu und aufregend

sortieren. Massenweise Algorithmen, die Sie noch nie gesehen haben. Ja, was tut man, wenn man was

sortiert? Was hat man für ein Problem? Ein Problem definiert sich durch eine Eingabe und eine Ausgabe,

nicht? Was haben wir als Eingabe? Ich sag mal abstrakt eine Sequenz, nicht? Das kann ein Array

sein, das kann eine verkettete Liste sein. Die heißt mal S und die besteht aus irgendwelchen

Einträgen E1 bis EN. Was diese Einträge sind, interessiert uns so gut wie gar nicht, bis auf

eine Tatsache. Die haben einen sogenannten Schlüssel und der Schlüssel dient dem Sortieren. Der

Schlüssel kann der Eintrag selber sein, nicht? Also wenn die Einträge einfach zum Beispiel, was weiß

ich, Wörter in einem Lexikon sind, dann, das war jetzt ein schlechtes Beispiel, denn im Lexikon habe

ich gerade mehr dran hängen als nur das Wort. Also sagen wir mal, wenn das einfach irgendwelche

Zahlen sind, die zufällig gerade aufsteigend sortieren sind, dann sind die Einträge selber die

Schlüssel. Im Allgemeinen ist also der Schlüssel irgendetwas, was ich aus dem Eintrag extrahiere,

also dafür gerade ist das Lexikon ein perfektes Beispiel. Ich habe einen langen Lexikoneintrag

und der Schlüssel ist das Wort selber und nach dem Wort, das vorne ansteht, sortiere ich. Ich

sage mal KI wäre der Schlüssel für II. So, nach den Schlüsseln will ich sortieren, das heißt auf

den Schlüsseln brauche ich irgendwie eine Vergleichsoperation und zwar sieht das so aus.

Auf den Schlüsseln habe ich eine sogenannte lineare Prä-Ordnung. Das was sie daran nicht

kennen ist das Wort Prä. Eine lineare Ordnung, was das ist, sollte jeder wissen. Eine Ordnung ist

eine reflexive transitive antisemitische Relation und eine lineare Ordnung ist der Begriff, der aus

einer Ordnung das macht, was man sich normalerweise naiv unter einer Ordnung vorstellt, nämlich etwas,

wo immer zwei Elemente untereinander vergleichbar sind, was ich also gewissermaßen auf einer Linie

anordnen kann, was also für eine Ordnung im Allgemeinen nicht der Fall ist. Ja, bei einer

Prä-Ordnung verzichten wir auf die Antisemitrie, das heißt, wenn wir das jetzt mal auflisten,

heißt das Folgendes, wir nennen das Ding mal kleiner gleich. So, das heißt kleiner gleich ist,

jetzt kommen drei Eigenschaften. Erstens ist es eine Prä-Ordnung, das heißt es ist zum einen

reflexiv. Ich lasse die Quantoren jeweils jetzt weg, also alles was ich jetzt hinschreibe mit

lauter freien Variablen drin ist implizit über diese freien Variablen allquantifiziert, also das

hier heißt für alle x ist x kleiner gleich x. Ferner ist sie transitiv. Wenn x kleiner

gleich y ist und y kleiner gleich z, dann ist x kleiner gleich z, nicht üblicher Begriff. So,

jetzt würde bei einer Linie an Ordnung noch kommen Antisemitrie, wenn x kleiner gleich y ist und y

auch kleiner gleich x, dann ist y schon gleich x, das genau verlangen wir hier nicht. So, wir

verlangen aber Linearität, das heißt wir verlangen, dass für jedes x und y gilt, dass

entweder x kleiner gleich y ist oder y kleiner gleich x. Also ich kann je zwei Elemente auf jeden

Fall vergleichen. Das brauche ich, zumindest um die Algorithmen, wie wir sie hier durchziehen zu

machen. Also im Allgemeinen braucht man das zum Sortieren nicht. Es gibt sogenanntes topologisches

Sortieren, wo ich also auch nach einer Ordnung sortieren kann, die diese Eigenschaft nicht erfüllt,

da ist dann das Ergebnis des Sortierens noch wesentlich unterbestimmter, als es hier sowieso

schon ist und insbesondere klappen dann auch die Algorithmen, die wir hier verwenden, nicht mehr

für topologisches Sortieren. So, und hier die Warnung, die also das auf das weggelassene Aktion verweist.

Also es kann vorkommen, dass Schlüssel ungleich sind, aber trotzdem einer kleiner gleich dem anderen

und umgekehrt. Das ist also bedingt durch das Weglassen dieses Antisemitrieaxiums. Also es

kann Elemente geben, also Schlüssel, die verschieden sind, aber für Zwecke des Sortierens äquivalent.

So, und diese Sortierung auf den Schlüsseln, also die Ordnung auf den Schlüsseln, die übertrage

ich auf die Einträge. Das heißt, ich schreibe ei kleiner gleich ej wann, naja gut, wenn dasselbe

eben für die entsprechenden Schlüssel gilt, das heißt, wenn KI kleiner gleich KJ ist. Ja, gut,

was ist die Ausgabe? Ja, die Ausgabe soll zwei Dinge erfüllen. Erstens soll sie natürlich sortiert

sein, also das ist gerade der Zweck der ganzen Sache, dass wir etwas sortieren. Naja, und sie

soll in einem bestimmten Sinne aber dieselbe Liste sein wie die, die wir reingesteckt haben.